class Solution {
public:
    struct cmp
    {
        bool operator()(const pair<string, int>& p1, const pair<string, int>& p2)
        {
            if(p1.second ==  p2.second) // 频次相同，字典序排序，小的在前，大根堆less
                return p1.first < p2.first;
            return p1.second > p2.second; // 频次大的在前->小根堆greater
        }
    };
 
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash;
        for(auto& e : words) // 字符和频次映射到哈希表
        {
            hash[e]++;
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap;
        for(auto& e : hash) // Topk主逻辑
        {
            heap.push(e);
            if(heap.size() > k)
                heap.pop();
        }
        vector<string> ret(k); // 提取结果返回
        for(int i = k - 1; i >= 0; --i)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};